package com.atguigui.leetcode;

/**
 * 915.分割数组
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/10/24 8:49
 */
public class P915PartitionArrayIntoDisjointIntervals {

    public static void main(String[] args) {
        Solution solution = new P915PartitionArrayIntoDisjointIntervals().new Solution();
        // TO TEST
    }

    class Solution {
        public int partitionDisjoint(int[] nums) {
            int n = nums.length;
            int leftMax = nums[0], leftPos = 0, curMax = nums[0];
            for (int i = 1; i < n - 1; i++) {
                curMax = Math.max(curMax, nums[i]);
                //leftPos 作为划分位置是非法的，左边的最大应该小于当前的
                //当所有右边的数满足大于leftMax，则划分完成
                if (nums[i] < leftMax) {
                    leftMax = curMax;
                    //不和发的划分，重新规划在一起
                    leftPos = i;
                }
            }
            return leftPos + 1;
        }
    }
}
